package cn.good.yan.sf.t4;

import java.util.LinkedList;

/**
 * 4 递归
 * 汉诺塔  -  有3个柱子 a b c  -  规则：1次只能移动一个圆盘、小圆盘不能在大圆盘上
 * 思想：
 * 如果是1个圆盘，  1a   -> c
 * 如果是2个圆盘，  1a   -> b  2a -> c  1b   -> c   (需要借助中介的柱子b)
 * 如果是3个圆盘，  12a  -> b  3a -> c  12b  -> c   (思想，先把12圆盘 - 移动到 b柱子上，再把3移动到第3个柱子上，中间12移动步骤就是上面的)
 * 如果是4个圆盘，  123a -> b  4a -> c  123b -> c   (思想，先把123圆盘 - 移动到 b柱子上，再把4移动到第3个柱子上，同上)
 *
 * @author shengren.yan
 * @create 2024-05-13
 */
public class Demo4 {

    // 3 个 柱子 a b c
    static LinkedList<Integer> a = new LinkedList<>();
    static LinkedList<Integer> b = new LinkedList<>();
    static LinkedList<Integer> c = new LinkedList<>();

    // 汉诺塔 - 初始化
    public static void inte(int n) {
        for (int i = n; i >= 1; i--) {
            a.addLast(i);
        }
    }

    // 移动  ， 规则    A - B ,  A - C ,  B - C
    // 12a  -> b  3a -> c  12b  -> c
    public static void remove(int n,
                              LinkedList<Integer> a,
                              LinkedList<Integer> b,
                              LinkedList<Integer> c) {

        // n = 0,代表 a里都移动完了
        if (n == 0) {
            return;
        }

        remove(n - 1, a, c, b);
        c.addLast(a.removeLast());

        System.out.println("--- ------ ---");
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
        remove(n - 1, b, a, c);
    }

    public static void main(String[] args) {
        // 3 代表有：初始化有几个圆盘
        inte(3);
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
        System.out.println("--- 开始---");

        remove(3, a, b, c);
    }

}
